#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

// 大/小根堆解决topk问题
// 1、先任意取k个元素，构建大/小根堆
// 2、遍历剩余元素，与堆顶元素比较，若大/小于堆顶元素，则跳过，否则替换堆顶元素，调整堆，其中调整时间复杂度为O(logk)
// 3、遍历结束后，堆中元素即为topk元素

// c++ 中的优先级队列默认为大根堆

int main()
{
    srand(time(NULL));
    vector<int> vec;
    for (size_t i = 0; i < 10000; i++)
    {
        vec.push_back(rand() % 10000);
    }

    
    int topk = 10;
    // 获取最小的十个元素，采用大根堆
    priority_queue<int> pq;

    // 构建大根堆
    for (size_t i = 0; i < topk; i++)
    {
        pq.push(vec[i]);
    }
    
    // 遍历剩余元素，与堆顶元素比较，若大/小于堆顶元素，则跳过，否则替换堆顶元素，调整堆
    for (size_t i = topk; i < vec.size(); i++)
    {
        if (vec[i] > pq.top())
        {
            pq.pop();
            pq.push(vec[i]);
        }
    }
    

    // 遍历结束后，堆中元素即为topk元素
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }

    cout << endl;
    cout << "minpq" << endl;
    // 获取最大的十个元素，采用小根堆
    priority_queue<int, vector<int>, greater<int>> minpq;
    // 构建小根堆
    for (size_t i = 0; i < topk; i++)
    {
        minpq.push(vec[i]);
    }
    // 遍历剩余元素，与堆顶元素比较，若大/小于堆顶元素，则跳过，否则替换堆顶元素，调整堆
    for (size_t i = topk; i < vec.size(); i++)
    {
        if (vec[i] < minpq.top())
        {
            minpq.pop();
            minpq.push(vec[i]);
        }
    }
    

    // 遍历结束后，堆中元素即为topk元素
    while (!minpq.empty())
    {
        cout << minpq.top() << " ";
        minpq.pop();
    }  

    return 0;
}